/*
 * p1169.cpp
 *
 *  Created on: 2013-10-3
 *      Author: zy
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn = 100000 + 10;

int x[maxn], y[maxn];
int total_dist[maxn], total_weight[maxn], dist2[maxn];
int q[maxn], dp[maxn];

int func(int i)
{
	return dp[i] - total_dist[i + 1] + dist2[i + 1];
}

int main()
{
	int T, c, n, w, front, rear;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &c, &n);
		total_dist[0] = total_weight[0] = x[0] = y[0] = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d%d", &x[i], &y[i], &w);
			dist2[i] = abs(x[i]) + abs(y[i]);
			total_dist[i] = total_dist[i - 1] + abs(x[i] - x[i - 1]) + abs(y[i]
					- y[i - 1]);
			total_weight[i] = total_weight[i - 1] + w;
		}
		front = rear = 1;
		for (int i = 1; i <= n; i++)
		{
			while (front <= rear && total_weight[i] - total_weight[q[front]]
					> c)
				front++;//窗口左移
			dp[i] = func(q[front]) + total_dist[i] + dist2[i];
			while (front <= rear && func(i) <= func(q[rear]))
				rear--;//保持队列单调递增（删除队列中的无用元素）
			q[++rear] = i;//当前元素加入队列
		}
		printf("%d\n", dp[n]);
		if (T > 0)
			puts("");
	}
	return 0;
}
